/**
 * Copyright (C) 2013-2017 wxyz <hyhjwzx@126.com>
 * <p/>
 * This program can be distributed under the terms of the GNU GPL Version 2.
 * See the file LICENSE.
 */
package ren.wxyz.algorithm.i2a3.chapter02;

/**
 * 插入排序的实现
 *
 * @author wxyz 2017-09-03_20:58
 * @since 1.0
 */
public abstract class InsertionSort {

    /**
     * 非降序排序
     *
     * @param a 要排序的数组
     * @return 返回排序后的数组
     */
    public static int[] notDescendSort(final int[] a) {
        if (null == a) {
            return null;
        }
        if (a.length == 1) {
            return a;
        }

        // 步进索引
        int j;
        // 关键词
        int key;

        // 依次遍历
        for (j = 1; j < a.length; j++) {
            // 取出值
            key = a[j];
            // 计算循环不变式的上标
            int i = j - 1;
            // 找到插入的位置
            while (i > -1 && a[i] > key) {
                a[i + 1] = a[i];
                i--;
            }
            // 插入值
            a[i + 1] = key;
        }

        return a;
    }

    /**
     * 非升序排序
     * <br>
     *     来自练习 2-1-2
     *
     * @param a 要排序的数组
     * @return 返回排序后的数组
     */
    public static int[] notAscendSort(final int[] a) {
        if (null == a) {
            return null;
        }
        if (a.length == 1) {
            return a;
        }

        // 步进索引
        int j;
        // 关键词
        int key;

        // 依次遍历
        for (j = 1; j < a.length; j++) {
            // 取出值
            key = a[j];
            // 计算循环不变式的上标
            int i = j - 1;
            // 找到插入的位置
            while (i > -1 && a[i] < key) {
                a[i + 1] = a[i];
                i--;
            }
            // 插入值
            a[i + 1] = key;
        }

        return a;
    }

    /**
     * 线性查找
     * <br>
     *     来自练习 2-1-3
     *
     * @param a 被查找的数组
     * @param v 要查找的值
     * @return 返回 v 在数组中的位置；找不到，则返回 -1
     */
    public static int indexOf(final int[] a, int v) {
        if (null == a) {
            return -1;
        }

        for (int i = 0; i < a.length; i++) {
            if (v == a[i]) {
                return i;
            }
        }

        return -1;
    }
}
